package leetcode.biweekly.week101;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

//Solution3Test
public class Solution3 {

	public long makeSubKSumEqual(int[] arr, int k) {
		int len = arr.length;
		boolean[] add = new boolean[len];
		long ans = 0;
		for (int i = 0; i < arr.length; i++) {
			if (!add[i]) {
				List<Integer> cur = new ArrayList<>();
				int p = i;
				while (!add[p]) {
					cur.add(arr[p]);
					add[p] = true;
					p = (p + k) % len;
				}
				Collections.sort(cur);
				int m = cur.get(cur.size() / 2);
				for (int num : cur) {
					ans += Math.abs(m - num);
				}
			}
		}
		return ans;
	}

}
